package com.algrithom.tree.huffman;

import java.util.HashMap;
import java.util.Map;

import lombok.Getter;
import lombok.Setter;

/**
 * 霍夫曼树类
 *
 * @author think
 * @version 1.0.0
 */
public class HuffmanTree {
    
    @Getter
    @Setter
    private HuffmanNode root;
    
    /**
     * 该霍夫曼树对应的字符编码集
     */
    @Getter
    private final Map<String,String> codeSet = new HashMap<>();
    
    HuffmanTree(HuffmanNode root){
        this.root = root;
        // 初始化编码集
        buildCodeSet(root,"");
    }
    
    /**
     * 生成编码集的私有方法，运用了迭代的思想 参数currentNode表示当前节点，参数currentCode代表当前节点对应的代码
     *
     * @param currentNode HuffmanNode
     * @param currentCode HuffmanNode
     */
    private void buildCodeSet(HuffmanNode currentNode,String currentCode){
        if (currentNode.getKey() != null) {
            // 霍夫曼树中，如果当前节点包含关键字，则该节点肯定是叶子节点，将该关键字和代码放入代码集
            this.codeSet.put(currentNode.getKey(),currentCode);
        } else { // 如果不是叶子节点，必定同时包含左右子节点，这种节点没有对应关键字
            // 转向左子节点需要将当前代码追加0
            buildCodeSet(currentNode.getLeft(),currentCode + "0");
            // 转向右子节点需要将当前代码追加1
            buildCodeSet(currentNode.getRight(),currentCode + "1");
        }
    }
}
